home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / newmat.exe / NEWMAT.TEX < prev    next >
Text File  |  1991-07-30  |  23KB  |  680 lines
  1. //$$ newmat.tex            Documentation file
  2.  
  3. MATRIX PACKAGE                                          30 July, 1991
  4.  
  5. Copyright (C) 1991: R B Davies and DSIR
  6.  
  7. Permission is granted to distribute but not to sell.
  8.  
  9.  
  10. Introduction
  11. ------------
  12.  
  13. This is a description of an experimental matrix package. The package is
  14. an upgrade of one I distributed to a number of people in 1990.
  15.  
  16.  
  17. The package supports matrix types
  18.  
  19. Matrix                       (rectangular matrix)
  20. UpperTriangularMatrix
  21. LowerTriangularMatrix
  22. DiagonalMatrix
  23. SymmetricMatrix
  24. RowVector                    (derived from Matrix)
  25. ColumnVector                 (derived from Matrix).
  26.  
  27. Only one element type is supported.
  28.  
  29. The package includes the operations *, +, -, inverse, transpose,
  30. conversion between types, submatrix, determinant, Cholesky and
  31. Householder triangularisation.
  32.  
  33.  
  34. This description begins with some general notes on matrix packages, then
  35. a general description of my package and a list of features and problems.
  36. This is followed by details where you can get a copy and the detailed
  37. documentation.
  38.  
  39.  
  40. What we want from a matrix package
  41. ---- -- ---- ---- - ------ -------
  42.  
  43. A matrix package needs to provide
  44.  
  45. 1.   Evaluation of matrix expressions in a form familiar to
  46.      scientists and engineers. For example  A = B * (C + D.t());
  47. 2.   Access to the elements of a matrix;
  48. 3.   Access to submatrices;
  49. 4.   Common elementary matrix functions such as determinant and trace;
  50. 5.   A platform for developing advanced matrix functions such as eigen-
  51.      value analysis;
  52. 6.   Good efficiency and storage management.
  53. 7.   Graceful exit from errors.
  54.  
  55. It may also provide
  56.  
  57. 8.   A variety of types of elements (eg real and complex);
  58. 9.   A variety of types of matrices (eg rectangular and symmetric);
  59.  
  60. It may target small matrices (say 3 x 3), or medium sized matrices, or
  61. very large matrices.
  62.  
  63. I do not believe one can build a matrix package that will meet
  64. everyone's requirements. In many cases if you put in one facility, you
  65. impose overheads on everyone using the package. This both is storage
  66. required for the program and in efficiency. Likewise a package that is
  67. optimised towards handling large matrices is likely to become less
  68. efficient for very small matrices where the administration time for the
  69. matrix may become significant compared with the time to carry out the
  70. operations.
  71.  
  72. It is better to provide a variety of packages (hopefully compatible) so
  73. that most users can find one that meets their requirements. My package
  74. is intended to be one of these packages; but not all of them.
  75.  
  76. I don't think it is obvious what is the best way of going about
  77. structuring a matrix package. And I don't think you can figure this
  78. out with "thought" experiments. Different people have to try out
  79. different approaches. And someone else may have to figure out which is
  80. best. Or, more likely, the ultimate packages will lift some ideas from
  81. each of a variety of trial packages. So, I don't claim my package is an
  82. "ultimate" package, but simply a trial of a number of ideas.
  83.  
  84. But I do hope it will meet the immediate requirements of some people who
  85. need to carry out matrix calculations.
  86.  
  87.  
  88. The present package
  89. --- ------- -------
  90.  
  91. The package described here is intended to meet the requirements of
  92. someone carrying out statistical analysis and related calculations.
  93.  
  94. Specifically it caters for rectangular matrices, upper and lower
  95. triangular matrices, diagonal matrices, symmetric matrices, and row and
  96. column vectors. Only one element type (either float or double) is
  97. allowed. A later version may include band matrices and/or a limited
  98. sparse matrix capability.
  99.  
  100. It is intended for matrices in the range 4 x 4 to about 80 x 80. The
  101. upper limit is imposed by the maximum number of elements that can be
  102. contained in a single array (8000 doubles in some machines). 
  103.  
  104. Operations provided include +, -, *, inverse, transpose, scaling by a
  105. scalar, conversion between types, submatrix, determinant, trace, sum of
  106. squares of elements, Householder triangularisation, Cholesky
  107. decomposition. Singular value decomposition is to come but is not in the
  108. present package.
  109.  
  110. The package is designed for version 2.0 of C++. It works with Sun C++,
  111. Turbo C++, Borland C++, Glockenspiel C++ (2.00a) on a PC. There are
  112. problems with Zortech C++ (version 2.12) and JPI C++.
  113.  
  114.  
  115. Features
  116. --------
  117.  
  118. Matrix expressions are evaluated in two stages. In the the first stage a
  119. tree representation of the expression is formed. For example (A+B)*C is
  120. represented by
  121.  
  122.                     *
  123.                    / \
  124.                   +   C
  125.                  / \
  126.                 A   B
  127.  
  128. The expression is evaluated recursively during the second stage. The two
  129. stage approach means that an expression can be scanned before evaluation
  130. and the best method of evaluation found.
  131.  
  132. The package recognises combinations of the form  A.i()*B  where i() is
  133. the inverse operation and avoids evaluating the inverse explicitly.
  134.  
  135. The package recognises and takes advantage of a matrix appearing on both
  136. sides of an '=' as in  A=B-A; resulting in faster execution and less
  137. temporary storage.  There is no need to provide an operator += since 
  138. A=A+B  is automatically recognised as an "add into" operation.
  139.  
  140. Matrices generated temporarily when an expression is evaluated are
  141. destroyed or recycled as soon as their values are no longer required.
  142. Each matrix has a tag which indicates if it is temporary so that its
  143. memory is available for recycling or deleting.
  144.  
  145. Further possibilities not yet included are to recognise A.t()*A and
  146. A.t()+A as symmetric or to improve the efficiency of evaluation of
  147. expressions like A+B+C, A*B*C, A*B.t()  [t() denotes transpose].
  148.  
  149. The package attempts to solve the problem of the large number of
  150. versions of the binary operations required when one has a variety of
  151. types. With n types of matrices the binary operations will each require
  152. n-squared separate algorithms. Some reduction in the number may be
  153. possible by carrying out conversions. However the situation rapidly
  154. becomes impossible with more than 4 or 5 types.
  155.  
  156. In this package each matrix type includes routines for extracting
  157. individual rows or columns. Only a single algorithm is then required for
  158. each binary operation. The rows can be located very quickly since most
  159. of the matrices are stored row by row. Columns must be copied and so the
  160. access is somewhat slower. The alternative approach of using iterators
  161. will be slower since the iterators will involve virtual functions.
  162.  
  163. In fact, I provide two algorithms for operations like + . If one is
  164. adding two matrices of the same type then there is no need to access the
  165. individual rows or columns and a faster general algorithm is
  166. appropriate.
  167.  
  168. The original version of the package did not use this access by row or
  169. column method and provided the multitude of algorithms for the
  170. combination of different matrix types. The code file length turned out
  171. to be just a little longer than the present one when providing the same
  172. facilities with 5 distinct types of matrices. It would have been very
  173. difficult to increase the number of matrix types in the original
  174. version. Apparently 4 to 5 types is about the break even point for
  175. switching to the approach adopted in the present package.
  176.  
  177.  
  178. Problems and limitations
  179. -------- --- -----------
  180.  
  181. The package does not have graceful exit from errors. There seems little
  182. point in developing this until exceptions become available in C++.
  183.  
  184. The package does not have delayed copy. In most situations this is not a
  185. significant disadvantage. It is a problem with functions returning a
  186. matrix; see the detailed documentation.
  187.  
  188. The package does not readily handle matrices declared constant. Every
  189. operation must have the option of recycling the memory of matrices in
  190. its arguments. So it is not possible to declare these arguments as
  191. constant. It is too complicated to declare versions of each operation
  192. for constant and non-constant arguments and there doesn't seem to be a
  193. way of doing automatic conversions. In the presen